package com.example.demo.leetcode.top;

import java.util.Stack;

/**
 *
 * 有A,B,C三个点， 将A上的n个盘子移动到C，小的在上，大的在下
 *
 * 假设 A B C 对应 from other to
 * 1. 当只有一个盘子， 直接from - >to
 * 2. 当有n个盘子(n>1),
 * (2.1) 将from上的 n-1个盘子借助to，移动到other
 * (2.2)将一个盘子从from到to
 * (2.3) 将other上的 n-1个盘子 借助from 到 to
 *
 *
 * @date 2021/1/21 9:46
 **/
public class Digui_汉诺塔 {



    // n个盘 from-》to 借助other
    public static void move(int n,Stack from,Stack other,Stack to){
        if(n<1){
            return;
        }
        if(n==1){
            //a-->c
            to.push(from.pop());
        }else{
            move(n-1,from,to,other);
            to.push(from.pop());
            move(n-1,other,from,to);
        }
    }

    public static void main(String[] args) {


         Stack<String> A = new Stack<>();
         Stack<String> B = new Stack<>();
         Stack<String> C = new Stack<>();

        A.push("1");
        A.push("2");
        A.push("3");
        move(3,A,B,C);
        System.out.println(C.size());
    }


}
